package 剑指offer;

import 抽象数据类型.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;

import static 抽象数据类型.TreeNode.buildTree;

/**
 * @description: 给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。
 * 这个路径的开始节点和结束节点可以是二叉树中的任意节点
 * 例如：
 * 给出以下的二叉树，
 * @author: ywk
 * @date: 2020-11-04
 */
public class 二叉树的最大路径和 {
    public static void main(String[] args) {
        Integer[] str = new Integer[]{3, -1, 3, null, null, 1, 2};
        TreeNode treeNode = buildTree(new ArrayList<>(Arrays.asList(str)));
        System.out.println(maxPathSum(treeNode));

    }

    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    static int maxValue = 0;
    public static int maxPathSum (TreeNode root) {
        // write code here
        if(root==null) return 0;
        maxValue = Integer.MIN_VALUE;
        getMaxPathSum(root);
        return maxValue;
    }

    public static int getMaxPathSum(TreeNode root){
        if(root==null) return 0;
        int left = Math.max(0,getMaxPathSum(root.left));
        int right = Math.max(0,getMaxPathSum(root.right));
        maxValue = Math.max(maxValue,(Integer) root.val+left+right);
        return Math.max(0,(Integer)root.val+Math.max(left,right));
    }
}
